This invention is directed generally to techniques for analyzing physical phenomenon, including products or physical systems which are definable in terms of systems of linear equations. Specifically, the invention relates to operating a multiprocessor in a manner to efficiently analyze manufactured products or physical systems represented by such systems of equations. One such technique involves a machine implemented method for loading and storing a matrix which characterizes, in part, such a product or physical system into the memory of a network of processing cells. More specifically, the invention relates to a method and apparatus for loading and storing a large, sparse matrix which characterizes a physical system in a form that makes it more efficiently manipulated by a plurality of interconnected processors each having its own storage and capable of operation in a highly parallel manner. The invention is also directed to a machine-implemented method and apparatus for analyzing manufactured products and/or physical phenomenon through performing matrix operations, to solve systems of linear equations and thereby enable the more accurate design of such products and the better implementation, understanding, and use of physical systems in general.
Many physical systems may be described mathematically in terms of systems of linear equations which, in turn, are solved by matrix manipulation methods. Finite element analysis is a method concerned with describing various physical systems in terms of systems of equations and developing methodologies for the solution of such systems. The term "physical system" is meant herein to refer to structure, devices, apparatus or bodies of matter (solid, liquid, gas) or simply a region of space in which a particular physical, chemical or other phenomenon is occurring. Finite element analysis had it beginnings as a method for structural analysis, but today is routinely used in the design of motors, generators, magnetic resonance imaging systems, aircraft engine ignition systems, circuit breakers and transformers, to name but a few; its techniques are used to analyze stress, temperature, molecular structure, electromagnetic fields, current, physical forces, etc. in all sorts of physical systems. It has become a standard part of the design cycle for numerous products which are not easily analyzed by other methods. The present invention has particular application in the analysis and design of such products.
Systems of linear equations required to be solved by finite element analysis techniques are very often large and complex and for that reason computationally difficult to solve. For example, a system of equations from a large, but not untypical, two-dimensional finite element analysis may have 25,000 unknowns. Where such equations are based on a finite element mesh having contributions from a majority of nodes, no choice exists but to use brute computational force to arrive at a solution. In some instances, however, such equations are both large and sparse and, thereby, afford an opportunity to pretreat or transform the equations in a manner which makes them less computationally intensive to solve. The word "sparse" is used herein to refer to the characteristic that only a very small percentage of the elements in a matrix have non-zero values. When extreme sparcity exists in a very large system, several techniques exist which may be used to transform the system of equations into one which is more easily handled from a computational standpoint. However, in spite of such transformations, standard computational techniques may be either impractical or very inefficient depending on the size and other characteristics of the resulting matrix equations.
As one can understand from the above discussion, the field of finite element analysis has developed in large measure because of the availability of larger and more powerful computing machines for use in solving such systems. There now exist a variety of high performance, special purpose computer systems designed to perform special application calculations which are especially taxing to perform on general-purpose computers. One such system is based on the concept of a systolic architecture and provides a general methodology for mapping high-level computations into hardware structures. In a systolic system, data flows from the computer memory in a rhythmic fashion, passing through many processing elements in a chain or pipeline manner before returning to memory, thereby permitting multiple computations for each memory access and resulting in a great increase in the speed of execution of computationally intensive problems without an associated increase in input/output requirements. Some methodologies for tailoring systolic architectures to handle matrix operations are discussed in a paper by H. T. Kung and C. E. Leiserson entitled "Systolic Arrays (for VLSI)", Sparse Matrix Proc. 1978, Society for Industrial and Applied Mathematics, 1979, pp. 256-282. Another analysis of this problem and a suggested solution is addressed in the article in IEEE Transactions on Computers, Vol. C-32, No. 3, March 1983 entitled "An Efficient Parallel Algorithm for the Solution of Large Sparse Linear Matrix Equations".
The method of the invention results in storage of a matrix in a multiple processor architecture in a manner which makes it readily available for a variety of matrix operations. One such operation is back-substitution used in solving systems of linear equations which is specifically described herein, but others would suggest themselves to those skilled in the art having knowledge of the matrix storage technique described herein.
The matrix storage techniques of this invention may be implemented on a variety of parallel multiprocessor architectures, as alluded to hereinbefore. However, the use of the matrix storage method herein will be specifically described in connection with the back-substitution operation carried out on systolic array architecture as generally described in the paper by E. Arnould et al. entitled "A Systolic Array Computer" presented at the IEEE International Conference on Acoustics, Speech, and Signal Processing", Mar. 26-29, 1985, pp. 232-235. The method of the invention may be carried out on apparatus shown and described in U.S. Pat. No. 4,493,048 entitled "Systolic Array Apparatuses for Matrix Computations" issued in the name of H. T. Kung et al., the disclosure of which is hereby incorporated by reference.